exception ErrorNotFound ;

signature LIST_OPS =
sig
	val equals: ''a list * ''a list -> bool ;
	val search: ''a * ''a list -> int ;
	val find: ''a * ''a list -> int ;
end ;

signature SET_OPS =
sig
	val is_member: ''a * ''a list -> bool ;
	val is_superset: ''a list * ''a list -> bool ;
	val is_subset: ''a list * ''a list -> bool ;
	val equals: ''a list * ''a list -> bool ;
	val subtract: ''a list * ''a list -> ''a list ;
	val unite: ''a list * ''a list -> ''a list ;
	val intersect: ''a list * ''a list -> ''a list ;
end ;

structure ListOps =
struct
	fun equals([], []) = true
	|	equals(hx::tx, hy::ty) = (hx = hy) andalso equals(tx, ty)
	|	equals(_, _) = false ;

	fun	find(_, []) = raise ErrorNotFound
	|	find(x, y :: S) =
			if x = y
				then 0
				else 1 + find(x, S) ;

	fun search(x, S) = find(x, S)
		handle ErrorNotFound => ~1 ;
end; (* of structure ListOps *)

structure SetOps: SET_OPS =
struct

	fun	is_member(x, S) = ListOps.search(x, S) >= 0 ;

	fun	subtract([], _) = []
	|	subtract(x :: A, B) =
			if is_member(x, B)
				then subtract(A, B)
				else x :: subtract(A, B) ;

	fun	is_superset(_, []) = true
	|	is_superset([], _) = false
	|	is_superset(A, x :: B) = is_member(x, A) andalso is_superset(A, B) ;

	fun	is_subset(A, B) = is_superset(B, A) ;

	fun	equals(A, B) = is_superset(A, B) andalso is_subset(A, B) ;

	fun	unite([], small) = small
	|	unite(big, []) = big
	|	unite(big, x :: small) =
			if is_member(x, big)
				then unite(big, small)
				else x :: unite(big, small) ;

	fun	intersect(_, []) = []
	|	intersect([], _) = []
	|	intersect(A, x :: B) =
			if is_member(x, A)
				then x :: intersect(A, B)
				else intersect(A, B) ;
end; (* of structure SetOps *)

fun andmap f nil = true
  | andmap f (a :: s) = (f a) andalso (andmap f s);

fun ormap f nil = false
  | ormap f (a :: s) = (f a) orelse (ormap f s);

